一种复杂网络路由策略的普适优化算法

现有的复杂网络路由策略很多,改进算法也不断涌现,但是目前还没有一个统一的标准来衡量算法是否达到网络最佳传输效果.针对这一问题,本文提出一种适用于现有路由策略的普适优化算法.首先通过理论分析指出制约网络传输能力的关键因素是最大介数中心度,因而"最大介数中心度是否已经最低"成为评判路由策略是否最优的标准.在此基础上,采用"惩罚选择法"避开网络中介数中心度值比较大的节点,使网络介数中心度值分布更均匀,均衡网络中各个节点的传输负载.仿真结果显示,该优化算法针对现有路由策略均能降低最大介数中心度值,大幅度提高网络的传输能力.     

Analysis of scalability for AODV routing protocol in wireless sensor networks

This paper presents preliminary work to address scalability concern over AODV protocol in wireless sensor network. Firstly, we discussed the scalability design issues with related work in context of wireless sensor networks (WSN). Following, we designed and illustrated wireless sensor network model. Finally, significance of scalability on the behaviour of application, MAC, transport and physical layer performance is described.     

神经网络在平面布线 中的应 用

Hopfield给出N个节点完全图K，中求最短Hamilton圈的神经网络方法，若将无自环图看做K，的子图，不难求出Hamilton图的Hamilton圈.不过当节点数增多时，解神经网络动态方程常得到次优解，和Hamilton圈差一两条边，称为准Hamilton圈.利用Hamilton圈和准Hamilton圈，可以画出一个平面图的平面化图，或者将一个非平面图分解为平面化子图，以便平面布线.     

A mathematical model of deterministic wormhole routing in hypercube multicomputers using virtual channels

Although several analytical models have been proposed in the literature for binary n-cubes with deterministic routing, most of them have not included the effects of virtual channel multiplexing on network performance. The only mathematical model for deterministic wormhole routing in hypercubes with virtual channels was proposed in [Y. Boura, Design and Analysis of Routing Schemes and Routers for Wormhole-routed Mesh Architectures, Ph.D. Thesis, Department of Computer Science and Engineering, Pennsylvania State University, 1995] which uses complex combinatorial analysis with a computation time of O(N=2ⁿ) for an n-dimensional hypercube. This paper proposes a new and simple analytical model to compute message latency in binary n-cubes with virtual channels. It is very simple and easy to understand which uses an average case analysis and requires a computation time of O(n) for an n-dimensional hypercube. Results from simulation experiments confirm that the proposed model exhibits a good degree of accuracy for various network sizes and under different operating conditions.     

Improvement of packet transmission scheduling and delivery rate in wireless Ad-Hoc networks

The principal purpose of Ad-Hoc wireless networks is to increase service efficiency in terms of transmission scheduling and packet transfer rate. The approaches that assume frame unicity to satisfy a given set of packets minimize the end-to-end delay. However, they do not guarantee a maximum packet delivery rate due to the difficulty of establishing robust paths for packet transfer across nodes deployed in the network, especially in a three-dimensional (3D) environment. The objective is to minimize the end-to-end delay by ensuring the maximum delivery of packets to their destinations. Furthermore, the signal-to-interference-and-noise-ratio (SINR) model is considered to optimize transmission scheduling. In this paper, an optimal node coordinates optimization approach is proposed to extend two recently investigated schemes in the literature (S-RDSP and I-RDSP). The developed algorithms, named S-MPDR and I-MPDR, seek to reduce the end-to-end delay by delivering a collection of inserted packets over a 3D environment while also maximizing the delivery rate of these packets. Desirability functions are used to evaluate the network’s performance in various scenarios involving two different environments, Level 0 and Level 1. Numerical results demonstrate that the developed algorithms outperform both schemes in terms of end-to-end delay and packet delivery rate. In the Level 0 environment, the overall minimum delay and packet delivery rate scores provided by S-MPDR are increased by 28% and 88% compared to S-RDSP, respectively. In comparison, those provided by I-MPDR are increased by 24% and 16% compared to I-RDSP. Similarly, in the Level 1 environment, the scores provided by S-MPDR are increased by 25% and 100% compared to S-RDSP, respectively, while those provided by I-MPDR are increased by 23% and 25% compared to I-RDSP.     

Few-photon routing via chiral light-matter couplings

A quantum router is one of the essential elements in the quantum network. Conventional routers only direct a single photon from one quantum channel into another. Here, we propose a few-photon router. The active element of the router is a single qubit chirally coupled to two independent waveguides simultaneously, where each waveguide mode provides a quantum channel. By introducing the operators of the scatter-free space and the controllable space, the output state of the one-photon and two-photon scattering are derived analytically. It is found that the qubit can direct one and two photons from one port of the incident waveguide to an arbitrarily selected port of the other waveguide with unity, respectively. However, two photons cannot be simultaneously routed to the same port due to the anti-bunch effect.     

State-Dependent Coupling in General Networks

In this paper we extend a result which holds for the class of networks of quasireversible nodes to a class of networks constructed by coupling Markov chains. We begin with a network in which the transition rates governing the stochastic behaviour of the individual nodes depend only on the state of the node. Assuming that the network has an invariant measure, we construct another network with transition rates at each node depending on the state of the entire network, and obtain its invariant measure.     

以商圈为中心的O2O动态外卖配送路径优化模型与算法

针对线上到线下(Online to Offline,O2O) 外卖路径优化问题,综合考虑其动态配送需求、货物区分等特点以及时间窗、载货量等约束条件,将商圈看作配送中心,将快递员数量与快递员总行驶时间作为最小化目标,提出了以商圈为中心的O2O动态外卖配送路径优化模型。采用周期性处理新订单的方法将相应的快递员路径的动态调整问题转化为一系列静态TSP子问题,设计了一种分阶段启发式实时配送路径优化算法框架,并给出了一个具体算法和一个数值计算实例。在VRP通用算例的基础上,以商圈为中心生成测试算例,对本文算法进行仿真实验,并与其他算法比较。结果表明：本文算法能充分利用新订单附近的快递员进行配送,并优化其配送路径,有效减少了快递员数量与快递员总行驶时间。     

Sampled-data distributed protocol for coordinated aggregation of multi-agent systems subject to communication delays

This paper studies the coordinated aggregation problem of a multi-agent system. Particularly, all the agents reach a consensus within a pre-specified target region. However, only a subset of agents have access to this target region, and each agent merely interacts with its neighbors by communication. Moreover, there exist unknown heterogeneous delays in communication channels. The underlying communication topology is characterized by a digraph. To accommodate the practical digital disposal, a sampled-data distributed protocol is proposed, where the sampling is asynchronous in the sense that the sampling periods of distinct agents are heterogeneous. The resulting closed-loop system from the proposed sampled-data distributed protocol is in a hybrid fashion that the continuous system is fed-back by using discrete states at sampling instants. The convergence performance of this hybrid closed-loop system is analyzed based on the contraction theory. More specifically, it is first shown that all the states are coordinated to aggregate within the target region, i.e., coordinated aggregation. With this result, it is next shown that all the states are coordinated towards a consensus, i.e., state agreement. These together guarantee the fulfillment of the concerned coordinated aggregation objective. Finally, a simulation example is given to validate the theoretical results.     

Constant-factor approximations for Capacitated Arc Routing without triangle inequality

Given an undirected graph with edge costs and edge demands, the Capacitated Arc Routing problem (CARP) asks for minimum-cost routes for equal-capacity vehicles so as to satisfy all demands. Constant-factor polynomial-time approximation algorithms were proposed for CARP with triangle inequality, while CARP was claimed to be NP-hard to approximate within any constant factor in general. Correcting this claim, we show that any factor  α$\alpha$ approximation for CARP with triangle inequality yields a factor  α$\alpha$ approximation for the general CARP.